# Definition for singly-linked list.
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 1.定义快慢指针
        fast = head  # 快指针
        slow = head  # 慢指针

        # 2.移动快慢指针
        while fast is not None and fast.next is not None:
            fast = fast.next.next  # 每次移动 2 个节点
            slow = slow.next  # 每次移动 1 个节点

        return slow


if __name__ == '__main__':
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)
    head.next.next.next.next.next = ListNode(6)

    s = Solution()
    node = s.middleNode(head)
    print(node.val)
